#region Using Statements
using System;
using System.Collections.Generic;
//using System.Xml.Serialization;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Storage;
#endregion

namespace Pauliver
{

    //could replace all the floats with one <T> and 1 delegate
    public class SortedList<T> 
    {
        public delegate Node<T> Comparison(Node<T> first, Node<T> second);
        public delegate float GetValue(T t);

        public class Node<TT>
        {
            public TT data;
            public float value;
            public Node<TT> Next;
            public Node<TT> Previous;
            public Node(float c, TT o)
            {
                data = o;
                value = c;
            }
        }

        Node<T> sorted;
        Comparison comparer;
        GetValue getvalue;

        public SortedList(List<T> scenegraph, GetValue value, Comparison c)
        {
            sorted = new Node<T>(value(scenegraph[0]), scenegraph[0]);
            comparer = c;
            getvalue = value;

            for(int i = 1; i < scenegraph.Count; ++i)
            {
                Node<T> n = new Node<T>(value(scenegraph[i]), scenegraph[i]);
                AttachNode(sorted,n);
            }
        }

        private void AttachNode(Node<T> RootNode,Node<T> atache)
        {
            if (RootNode.Equals(comparer(RootNode, atache)))
            {
                if (RootNode.Next == null)
                {
                    RootNode.Next = atache;
                    atache.Previous = RootNode;
                }
                else
                {
                    AttachNode(RootNode.Next, atache);
                }
            }
            else
            {
                if (RootNode.Previous == null)
                {
                    sorted = atache; //sorted is the root node
                    atache.Next = RootNode;
                    RootNode.Previous = atache;
                }
                else
                {   //insert between RootNode.previous and RootNode

                    atache.Next = RootNode;
                    atache.Previous = RootNode.Previous;
                    atache.Previous.Next = atache;
                    RootNode.Previous = atache;

                }
            }
        }

        public static Node<T> Greater(Node<T> RootNode, Node<T> atache)
        {
            if (RootNode.value > atache.value)
            {
                return RootNode;
            }
            return atache;
        }

        public static Node<T> Less(Node<T> RootNode, Node<T> second)
        {
            if (RootNode.value > second.value)
            {
                return RootNode;
            }
            return second;
        }

        public List<T> GetList()
        {
            List<T> L = new List<T>();
            Node<T> n = sorted;
            while(n != null)
            {
                L.Add(n.data);
                n = n.Next;
            }
            return L;
        }

    }
}
